#include <stdlib.h>
#include "fatal.h"
#include "Stack.h"

#include <stdio.h>

struct Node
{
    ElementType Element;
    PtrToNode Next;
};

int IsEmpty(Stack S)
{
    return S->Next == NULL;
}

Stack CreateStack(void)
{
    Stack S;
    S = malloc(sizeof(struct Node));
    if (S == NULL)
    {
        FatalError("Out of Space.");
    }
    S->Next = NULL;
    MakeEmpty(S);
    return S;
}

void DisposeStack(Stack S)
{
    MakeEmpty(S);
    free(S);
}

void MakeEmpty(Stack S)
{
    if (S == NULL)
    {
        Error("Must use CreateStack first");
    }
    while ( !IsEmpty(S) )
    {
        Pop(S);
    }
}

void Push(ElementType X, Stack S)
{
    Stack TmpStack;
    TmpStack = malloc(sizeof(struct Node));
    if (TmpStack == NULL)
    {
        FatalError("Out of Space.");
    }
    TmpStack->Element = X;
    TmpStack->Next = S->Next;
    S->Next = TmpStack;
}

ElementType Top(Stack S)
{
    if (IsEmpty(S))
    {
        Error("Empty Stack.");
    }
    return S->Next->Element;
}

void Pop(Stack S)
{
    Stack SubStack;
    if (IsEmpty(S))
    {
        Error("Empty Stack.");
    }
    SubStack = S->Next;
    S->Next = S->Next->Next; // 接上下下个节点
    free(SubStack);
}